package com.gao.util;

import java.util.NoSuchElementException;

/**
 * @author gao
 * @date 2023/08/28 10:16:51
 */
public class Heap<T extends Comparable<? super T>> implements Collection<T> {
    private ArrayList<T> list = new ArrayList<>();

    private Order order;

    public enum Order {
        MAX, MIN
    }

    public Heap() {
        this.order = Order.MAX;
    }

    public Heap(Order order) {
        this.order = order;
    }

    @Override
    public boolean add(T obj) {
        list.add(obj);
        heapUp(list.size() - 1);
//         makeHeap();
        return true;
    }

    @Override
    public boolean del(T val) {
        throw new UnsupportedOperationException();
    }

    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("堆是空的");
        }
        T maxElement = list.get(0);
        replaceMaxElementWithLastElement();
        heapDown(0);
        return maxElement;
    }

    private void replaceMaxElementWithLastElement() {
        T lastElement = list.get(list.size() - 1);
        list.set(0, lastElement);
        list.del(list.size() - 1);
    }

    @Override
    public Iterator<T> iterator() {
        return new HeapIterator<>();
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.size() == 0;
    }

    private void makeHeap() {
        for (int i = list.size() - 1; i >= 0; i--) {
            heapDown(i);
        }
    }

    private void heapDown(int i) {
        while (i < list.size()) {
            int extremeValueIndex = findExtremeValueIndexFromLeftChildAndRightChildAndSelf(i);

            if (extremeValueIndex == i) {
                /*
                    当前节点没有子节点，或者当前节点的值比左右子节点的值都大
                    此时不用继续向下调整了，直接跳出循环
                 */
                break;
            }

            // 交换下标为i和maxium的两个元素
            swap(i, extremeValueIndex);

            // 继续向下调整
            i = extremeValueIndex;
        }
    }

    private void heapUp(int i) {
        while (i > 0) {
            int parentIndex = (i - 1) / 2;
            if (compareValueByIndex(parentIndex, i)) {
                swap(i, parentIndex);
                i = parentIndex;
            } else {
                break;
            }
        }
    }

    private void swap(int i, int j) {
        T tmp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, tmp);
    }

    private int findExtremeValueIndexFromLeftChildAndRightChildAndSelf(int i) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int extremeValueIndex = i;

        if (left < list.size() && compareValueByIndex(extremeValueIndex, left)) {
            extremeValueIndex = left;
        }
        if (right < list.size() && compareValueByIndex(extremeValueIndex, right)) {
            extremeValueIndex = right;
        }
        return extremeValueIndex;
    }

    private boolean compareValueByIndex(int index, int index2) {
        return order.equals(Order.MAX) ? list.get(index).compareTo(list.get(index2)) < 0 : list.get(index).compareTo(list.get(index2)) > 0;
    }


    public class HeapIterator<T> implements Iterator<T> {
        private int index;

        @Override
        public boolean hasNext() {
            return index < list.size();
        }

        @Override
        public T next() {
            return (T) pop();
        }
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Iterator<T> it = iterator();
        while (it.hasNext()) {
            T elt = it.next();
            sb.append(elt);
            sb.append(",");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    public ArrayList<T> getList() {
        return list;
    }
}

